#include <bits/stdc++.h>
using namespace::std;

// 二分查找，数组要有序
// 上下界查找，先判断数据是否在数组范围内，解决界外不存在
// 获取索引后，判断数组在索引处数据是否等于被查找数，解决界内不存在
// 如果所查找数据存在，下界查找得到该数据第一个位置，上界查找得到该数据最后一个位置的下一个位置
// 如果所查找数据不存在，上下界查找返回相同的值，都是数据应该被插入的位置的索引 - 
// 数组中第一个大于它的数据的索引 [0, num.size()]，可能越上界
class Solution {
public:
    int searchLeft(vector<int>& nums, int target){
        if(target < nums.front() || nums.back() < target) return -1;

        int l = 0, r = nums.size();
        while(l < r){
            int mid = l + (r - l) / 2;
            if(target == nums[mid]){
                r = mid;
            }
            else if(target < nums[mid]){
                r = mid;
            }
            else if(nums[mid] < target){
                l = mid + 1;
            }
        }
        return l;
    }

    int searchRight(vector<int>& nums, int target){
        if(target < nums.front() || nums.back() < target) return -1;

        int l = 0, r = nums.size();
        while(l < r){
            int mid = l + (r - l) / 2;
            if(target == nums[mid]) l = mid + 1;
            else if(target < nums[mid]) r = mid;
            else if(nums[mid] < target) l = mid + 1;
        }
        return l;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1, -1};
        if(nums.size() == 1 && nums[0] == target) return {0, 0};
        if(nums.size() == 1 && nums[0] != target) return {-1, -1};

        int lid = searchLeft(nums, target);
        cout << lid << " ";
        if(lid != -1 && nums[lid] != target) lid = -1;
        
        int rid = searchRight(nums, target);
        cout << rid << endl;
        if(rid != -1 && nums[rid - 1] == target) rid -= 1;
        else rid = -1;

        return {lid, rid};
    }
};




int main(int argc, char const *argv[])
{
    Solution sol;

    vector<int> nums = {5,7,7,8,8,10};
    int target = 9;

    vector<int> res = sol.searchRange(nums, target);
    cout << res[0] << "-" << res[1] << endl;

    return 0;
}
